今天是練習如何用 C# 寫快速排序，想更瞭解快速排序概念的讀者，可以直接看參考資料的介紹 ~

概念

1. 從陣列中選出一個值作為基準值 (Pivot)，接著由資料的左方往陣列中間找比基準值大的值、右方往陣列中間找比基準值小的數值。找到後讓這兩個值交換位置。
2. 反覆地尋找並重複以上過程，直到左方和右方索引指到相同的位置。
3. 將基準值與索引位置上的值交換。
4. 從該位置將陣列分為較小和較大的兩個陣列，並回到步驟 1 繼續進行排序。

範例

using System;
					
public class Program
{
	public static void Main()
	{
		int[] ans = {5, 6, 3, 8, 1, 10, 9, 2};
		quicksort(ans, 0, ans.Length - 1);
		foreach(int a in ans){
			Console.Write(a + " ");
		}
	}
	
	// 快速排序
	public static void quicksort(int[] data, int left, int right)
	{
		if(left >= right){
			return;
		}
		
		// 排序過程
		int i = left, j = right, key = data[left];
		while(i != j){
			for(;data[j] > key && i < j; j -= 1);
			for(;data[i] <= key && i < j;i += 1);
			if(i < j){
				int temp = data[i];
				data[i] = data[j];
				data[j] = temp; 
			}
		}
		
		// 更換基準點
		data[left] = data[i];
		data[i] = key;
		
		// 遞迴處理未排序完成的部分
		quicksort(data, left, i - 1); 
		quicksort(data, i + 1, right);
	}
}

參考資料

• [演算法] 快速排序法 (Quick Sort) - iT 邦幫忙
• 個人 Github Pages